#pragma once
#include <cassert>
#include <cstddef>
#include <cstring>
#include <iostream>

template<class T>
class vector
{
    using iterator = T*;
    using const_iterator = const T*;
public:
    iterator begin()
    {
        return start_;
    }
    iterator end()
    {
        return finish_;
    }
    const_iterator begin() const
    {
        return start_;
    }
    const_iterator end() const
    {
        return finish_;
    }
    vector() = default;
    vector(std::initializer_list<T> il)
    {
        reserve(il.size());
        for (const auto &e : il)
            push_back(e);
    }
    vector(size_t n, const T &value = T())
    {
        resize(n, value);
    }
    template<class InputIterator, typename = std::_RequireInputIter<InputIterator>>
    vector(InputIterator first, InputIterator last)
    {
        while (first != last)
        {
            push_back(*first);
            ++first;
        }
    }
    vector(const vector<T> &v)
    {
        reserve(v.capacity());
        for (auto &e : v)
            push_back(e);
    }
    vector<T> &operator=(vector<T> v)
    {
        reserve(v.capacity());
        for (const auto &e : v)
            push_back(v);
    }
    ~vector()
    {
        if (start_)
        {
            delete[] start_;
            start_ = finish_ = endOfStorage_ = nullptr;
        }
    }
    void reserve(size_t n)
    {
        if (n > capacity())
        {
            size_t old_size = size();
            T *tmp = new T[n];
            if (start_)
            {
                // memcpy(tmp, start_, sizeof(T) * old_size);
                for (size_t i = 0; i < old_size; i++)
                    tmp[i] = start_[i];
                delete [] start_;
            }
            start_ = tmp;
            finish_ = start_ + old_size;
            endOfStorage_ = start_ + n;
        }
    }
    void resize(size_t n, T val = T())
    {
        if (n > size())
        {
            reserve(n);
            while (finish_ != start_ + n)
            {
                *finish_ = val;
                ++finish_;
            }
        }
        else
        {
            finish_ = start_ + n;
        }
    }
    T &operator[](size_t index)
    {
        assert(index < size());
        return start_[index];
    }
    const T &operator[](size_t index) const
    {
        assert(index < size());
        return start_[index];
    }
    void clear()
    {
        finish_ = start_;
    }
    const size_t size() const
    {
        return finish_ - start_;
    }
    const size_t capacity() const
    {
        return endOfStorage_ - start_;
    }
    void push_back(const T &x)
    {
        if (finish_ == endOfStorage_)
            reserve(capacity() == 0 ? 4 : capacity() * 2);
        *finish_ = x;
        ++finish_;
    }
    void pop_back()
    {
        assert(!empty());
        --finish_;
    }
    void insert(iterator pos, const T &x)
    {
        assert(pos >= start_ && pos <= finish_);
        if (endOfStorage_ == finish_)
        {
            size_t len = pos - start_;
            reserve(capacity() == 0 ? 4 : capacity() * 2);
            pos = start_ + len;
        }
        iterator end = finish_ - 1;
        while (end >= pos)
        {
            *(end + 1) = *end;
            --end;
        }
        *pos = x;
        ++finish_;
    }
    iterator erase(iterator pos)
    {
        assert(pos >= start_ && pos < finish_);
        iterator it = pos + 1;
        while (it != finish_)
        {
            *(it - 1) = *it;
            ++it;
        }
        --finish_;
        return pos;
    }
    bool empty() const
    {
        return start_ == finish_;
    }
private:
    iterator start_ = nullptr;
    iterator finish_ = nullptr;
    iterator endOfStorage_ = nullptr;
};